package JZ25_复杂链表的复制;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}

public class Solution {
    // 解决 Node 类型无法比较的问题
    static class NodeComparator implements Comparator<RandomListNode> {


        @Override
        public int compare(RandomListNode o1, RandomListNode o2) {
            return o1.hashCode() - o2.hashCode();
        }
    }
    public RandomListNode Clone(RandomListNode pHead) {
        RandomListNode newHead = new RandomListNode(-1);
        RandomListNode newLast = newHead;

        // 先复制链表（不处理random）
        for (RandomListNode cur = pHead; cur != null; cur = cur.next){
            RandomListNode node = new RandomListNode(cur.label);
            newLast.next = node;
            newLast = node;
        }

        // 建立映射关系
        Map<RandomListNode, RandomListNode> map = new TreeMap<>(new NodeComparator());
        RandomListNode oldCur = pHead;
        RandomListNode newCur = newHead.next;
        while (oldCur != null){
            map.put(oldCur, newCur);

            oldCur = oldCur.next;
            newCur = newCur.next;
        }

        // 处理 random 的问题
        oldCur = pHead;
        newCur = newHead.next;
        while (oldCur != null){
            RandomListNode oldRandom = oldCur.random;
            if (oldCur.random == null){
                newCur.random = null;
            } else {
                RandomListNode newRandom = map.get(oldRandom);
                newCur.random = newRandom;
            }

            oldCur = oldCur.next;
            newCur = newCur.next;
        }

        return newHead.next;
    }
}